package sjjg.graph;

import sjjg.tree.IndexMinPriorityQueue;
import sjjg.tree.MinPriorityQueue;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

public class DijkstraSP {
    private DirectedEdge[]edgeTo;//索引代表顶点 值代表从起点到该顶点最短路径的最后一条边
    private Double[]distTo;//索引代表顶点 值代表 从s到达顶点的最短路径的总权重
    private IndexMinPriorityQueue<Double>pq;//存放树中顶点与非树中顶点的有效横切边
    public DijkstraSP(WeightDirGraph G,int start){
           edgeTo=new DirectedEdge[G.V()];
           distTo=new Double[G.V()];
        for (int i = 0; i < distTo.length; i++) {
            distTo[i]=Double.MAX_VALUE;//一开始每个顶点之间的权重都为无穷大即不可达
        }
        pq=new IndexMinPriorityQueue<>(G.V());
        //默认0处为起点
        distTo[start]=0.0;
        pq.insert(start,distTo[start]);
        while (!pq.isEmpty()){
             relax(G,pq.delMin());
        }
    }
   public void relax(WeightDirGraph G,int v){//对顶点进行松弛
               //对顶点v的所有边进行松弛
       for (DirectedEdge directedEdge : G.adj(v)) {
            int w=directedEdge.to();
            if(distTo[v]+directedEdge.weight()<distTo[w]){//如果从起点到v再由v到w的权重和<由起点到w的最短路径 那么就更新数据
                distTo[w]=distTo[v]+directedEdge.weight();
                edgeTo[w]=directedEdge;
                if(pq.contains(w)){
                    pq.changeItem(w,directedEdge.weight());
                }else {
                    pq.insert(w,directedEdge.weight());
                }
            }
       }
    }
    public double distTo(int v){//起点到达v的最短路径的权重和
          return distTo[v];
    }
    public boolean hasPathTo(int v){//起点是否可达v
       return distTo[v]<Double.MAX_VALUE;
    }
    public Queue<DirectedEdge>pathTo(int v) {//返回起点到达v的最短路径
        if (!hasPathTo(v)) {
            return null;
        }
        Queue<DirectedEdge> mostShortPath = new LinkedBlockingQueue();
        //逆序遍历edgeTo
        while (true) {
            DirectedEdge directedEdge = edgeTo[v];
            if (directedEdge == null) {//到达起点
                break;
            }
            mostShortPath.add(directedEdge);
            v = directedEdge.from();
        }
        return mostShortPath;
    }
}
